package csm.uttils.generics;
import java.util.ArrayList;

/**
 *
 * @author Carlos S. Moreno
 */
public class treeAVL
{
    private treeNode raiz;

    public treeAVL ()
    {
       raiz = null;
    }

    public treeNode getRaiz()
    {
        return raiz;
    }

    public void setRaiz(treeNode r)
    {
        raiz = r;
    }

    public Comparable search (Comparable x)
    {
       if(x == null || (raiz != null && x.getClass() != raiz.getInfo().getClass())) return null;

       treeNode p = raiz;
       while (p != null)
       {
              Comparable y = p.getInfo();
              if (x.compareTo(y) == 0) { break; }
              if (x.compareTo(y) <  0) { p = p.getIzq(); }
              else { p = p.getDer(); }
       }
       return (p != null)? p.getInfo() : null;
    }


    public boolean add (Comparable x)
    {

       if(x == null || (raiz != null && x.getClass() != raiz.getInfo().getClass())) return false;

       treeNode p = raiz, q = null;
       while (p != null)
       {
            Comparable y = p.getInfo();
            if( x.compareTo(y) == 0 ) { break; }

            q = p;
            if ( x.compareTo(y) < 0 ) { p = p.getIzq(); }
            else { p = p.getDer(); }
       }

       // si ya exist�a... retorne false.
       if (p != null) return false;

       // si no exist�a... hay que insertarlo.
       treeNode nuevo = new treeNode(x, null, null);
       if (q == null) { raiz = nuevo; }
       else
       {
          if ( x.compareTo(q.getInfo() ) < 0) { q.setIzq(nuevo); }
          else { q.setDer(nuevo); }
       }
       return true;
    }

   public boolean remove (Comparable x)
    {
       if(x == null || (raiz != null && x.getClass() != raiz.getInfo().getClass())) return false;

       raiz = eliminar (raiz, x);
       return true;
    }

   public Object[] toPreOrden()
    {
       ArrayList l = new ArrayList<Comparable>();
       armarPreOrden(raiz, l);
       Object[] ar=new Object[l.size()];
       for(int i=0; i<ar.length;i++)
       {
           ar[i]=l.get(i);
       }
       return ar;
    }

   public Object[] toEntreOrdenAsc()
    {
       ArrayList l= new ArrayList<Comparable>();
       armarEntreOrdenAsc(raiz, l);
       Object[] ar=new Object[l.size()];
       for(int i=0; i<ar.length;i++)
       {
           ar[i]=l.get(i);
       }
       return ar;
    }
   public Object[] toEntreOrdenDesc()
    {
       ArrayList l= new ArrayList<Comparable>();
       armarEntreOrdenDesc(raiz, l);
       Object[] ar=new Object[l.size()];
       for(int i=0; i<ar.length;i++)
       {
           ar[i]=l.get(i);
       }
       return ar;
    }

   public Object[] toPostOrden()
    {
       ArrayList l= new ArrayList<Comparable>();
       armarPostOrden(raiz, l);
       Object[] ar=new Object[l.size()];
       for(int i=0; i<ar.length;i++)
       {
           ar[i]=l.get(i);
       }
       return ar;
    }

    private void armarPreOrden (treeNode p, ArrayList l)
    {
      if (p != null)
      {
        l.add(p.getInfo());
        armarPreOrden (p.getIzq(), l);
        armarPreOrden (p.getDer(), l);
      }
    }

    private void armarEntreOrdenAsc (treeNode p, ArrayList l)
    {
      if (p != null)
      {
        armarEntreOrdenAsc (p.getIzq(), l);
        l.add(p.getInfo());
        armarEntreOrdenAsc (p.getDer(), l);
      }
    }
    private void armarEntreOrdenDesc (treeNode p, ArrayList l)
    {
      if (p != null)
      {
        armarEntreOrdenDesc (p.getDer(), l);
        l.add(p.getInfo());
        armarEntreOrdenDesc (p.getIzq(), l);
      }
    }
    private void armarPostOrden (treeNode p, ArrayList l)
    {
      if (p != null)
      {
        armarPostOrden (p.getIzq(), l);
        armarPostOrden (p.getDer(), l);
        l.add(p.getInfo());
      }
    }

    private treeNode eliminar (treeNode p, Comparable x)
    {
       if (p != null)
       {
         Comparable y = p.getInfo();
         if ( x.compareTo(y) < 0 )
         {
             treeNode  menor = eliminar(p.getIzq(), x);
             p.setIzq(menor);
         }
         else
         {
              if ( x.compareTo(y) > 0 )
              {
                 treeNode mayor = eliminar (p.getDer(), x);
                 p.setDer(mayor);
              }
              else
              {
                 // Objeto encontrado... debe borrarlo.
                 if (p.getIzq() == null) { p = p.getDer(); }
                 else
                 {
                    if (p.getDer() == null) { p = p.getIzq(); }
                    else
                    {
                        // Tiene dos hijos... que lo haga otra!!!
                        treeNode dos = dosHijos(p.getIzq(), p);
                        p.setIzq(dos);
                    }
                 }
              }
         }
       }
       return p;
    }

    private treeNode dosHijos (treeNode d, treeNode p)
    {
       if (d.getDer() != null)
       {
         treeNode der = dosHijos(d.getDer(), p);
         d.setDer(der);
       }
       else
       {
         p.setInfo(d.getInfo());
         d = d.getIzq();
       }
       return d;
    }

    public Comparable Mayor()
    {
        Comparable c=null;
        treeNode p=raiz;
        while (p != null)
        {
            c=p.getInfo();
            p=p.getDer();
        }
        return c;
    }
    public Comparable Menor()
    {
        Comparable c=null;
        treeNode p=raiz;
        while (p != null)
        {
            c=p.getInfo();
            p=p.getIzq();
        }
        return c;
    }
}